The present invention is related to wireless networks, and in particular to a spanning tree protocol for use with an ad-hoc wireless network to avoid loops in the wireless network.
In the area of local area networks (LANs), and in particular, LAN bridges, spanning tree protocols are known for preventing loops in a bridged (typically wired) network. In particular, the Institute of Electrical and Electronics Engineers (IEEE) has developed a network communication standard IEEE 802.1d entitled, “Media Access Control (MAC) Bridges,” originally approved May 31, 1990 (hereinafter “IEEE 802.1d”), and also high-speed (IEEE 802.1w) and high-density (IEEE 802.1s) counterparts. Any of these protocols, and also a collection of these standard protocols is/are referred to herein as the “standard IEEE 802.1 spanning tree protocol.” In brief, the standard IEEE 802.1 protocol describes functions to be performed by a compliant bridge including maintaining the spanning tree topology for the bridge, building and maintenance of a filtering database, relaying and filtering of frames, and transmission of Bridge Protocol Data Units (BPDUs). A BPDU is a special message that bridges transmit to each other to facilitate determination of a spanning tree topology.
Wireless networks are becoming widespread. For example, wireless local area networks (WLANs) that conform to the IEEE 802.11 standard are becoming more and more popular. One way of operating a WLAN is in infrastructure mode according to which some wireless stations operate as access points, and each access point has client stations. All communication from and to a client station is via its access point. WLANS may also operate in ad-hoc mode according to which any station may communicate directly with any other station. Such a wireless network forms a mesh. The present invention is particularly applicable to such mesh wireless networks where, as in a wired mesh, any station could have a wireless link to another station. Such a network is also called a multi-hop wireless network herein.
The standard IEEE 802.1 spanning tree protocol was originally designed to work over wired Ethernet links and cannot operate until the low-level links are established. In wireless networks such as IEEE 802.11 networks, low-level link establishment is a multi-step process. The blocking/tearing down of established links by a spanning tree process such as used in a wired network may be undesirable. Thus, the standard IEEE 802.1 spanning tree protocol as designed cannot simply operate in a wireless network environment.
Implementations of the IEEE 802.1 spanning tree algorithms are common. It is desirable to not have to modify existing protocol stacks at end stations. Furthermore, it is desirable to not have to modify existing protocol stacks, such as mobile in ad-hoc mobile protocols (MANET protocols) and L3 routing logic in intermediate devices, common in Mobile-IP protocols.
It further is desirable to have a wireless spanning tree algorithm that avoids temporary loops. Temporary loops can be a problem in a bridged, multi-hop wireless network, often resulting in dramatically rapid packet proliferation through the network.
Described in the WSTP Application is how to operate, in a wireless network such as an IEEE 802.11-conforming network, a spanning tree protocol called WSTP (for wireless spanning tree protocol) herein, that substantially conforms to the standard IEEE 802.1 spanning tree protocol. By substantially conform we mean conforming to, including the extensions and modification in the WSTP Application and herein. The description in the WSTP Application is provided in terms of an IEEE 802.11 conforming network. WSTP is applicable to operations in a wireless standard that provides a mechanism for wireless stations to wirelessly communicate with other wireless stations using control/management frames for wireless network information, e.g., to transmit beacon or probe response frames to advertise the characteristics of the transmitting wireless station. The WSTP Application describes how in a wireless mesh network that includes a single portal, where by a portal is meant a node that has a connection (an uplink) to another network such as a LAN, WAN, e.g., the Internet, or a Satellite link, a spanning tree topology is formed in which the portal is the wireless bridging entity that forms the root of the tree. Wireless nodes that act as bridging nodes, called wireless Dbridges herein, advertise their spanning tree topology properties in the form of one or more bridge protocol data units (BPDUs) forming BPDU Information encapsulated in control/management frames, e.g., beacon and probe responses frames. The BPDU Information substantially conforms to standard IEEE 802.1 spanning tree protocol BPDU information and includes radio data. A wireless Dbridge advertises that it is a wireless Dbridge, i.e., that is WSTP-capable by sending management frames such as beacon frames that have a pre-defined field, called the “WSTP Capability” field herein, set to “true.” Other features of WSTP are described in the WSTP Application, and also herein below.
In a typical 802.11 mesh network, there are likely to be several, even many portals. In such a case, it may be preferable to run several instances of the wireless spanning tree protocol to generate several spanning tree topologies for scalability, with each portal forming a root bridge for a spanning tree topology of wireless Dbridges. Moreover, in order to provide the needed Quality of Service (QoS) and to provide for multicasting, it may be desirable to run several instances of the wireless spanning tree protocol to generate several tree topologies, all having the same portal as the root mesh point.
Thus there is a need in the art for a method and apparatus for running a mesh network that includes a running a plurality of instances of wireless spanning tree protocol in a wireless mesh network to generate a corresponding plurality of tree protocols. Some of the plurality of wireless spanning tree topologies may run laterally, meaning that the tree topologies run on different sets of devices, each one root mesh point, e.g., a portal device. Connecting the portal devices forms a mesh network of mesh networks.
In an alternate configuration, a plurality of wireless spanning tree protocol instances run on the same device to generate a corresponding plurality of topologies that have the same root bridge. The instances each has a different path cost metric. We call such a set of multiple wireless spanning tree topologies from running multiple wireless spanning tree protocol instances an overlaid network configuration. Such an overlaid network configuration provides for different quality of service QoS and for efficient multicasting per tree protocol.
Thus there is a need in the art for operating a wireless mesh network with an overlay wireless spanning tree protocol mechanism that greatly enhances the ability of differentiating different traffic classes in a mesh network, and that is able to provide pre-defined end-to-end quality of service (QoS) for each such class.
There further is a need in the art for so using a wireless spanning tree protocol in a scalable manner, with the scaling being flexible to suit different network and application requirements.
There also is a need in the art for operating a mesh network with an overlay wireless spanning tree protocol mechanism that provides for easily and effectively incorporating 802.11e QoS enhancements into the wireless spanning tree protocol.
There also is a need in the art for an overlay mechanism that significantly increases the efficiency of multicast forwarding in a mesh network and that re-uses existing multicasting protocols and methods whenever appropriate.